/*
https://leetcode.cn/problems/count-complete-tree-nodes/description/
222. 完全二叉树的节点个数
medium, 方钊堉 2024.09.17
二分查找
*/

class Solution {
public:
    int sum = 0; // 用于累加节点数量
    
    void judge(TreeNode* root) {
        if(!root) return;
        if(!root -> left && !root -> right) { sum+=1 ;return;}
        sum+= 1;
        int lqw = -1, rqw = -1;
        // 计算左子树的高度
        TreeNode* ki = root -> left;
        if(ki){
            ++lqw;
            while(ki -> left) {
            ++lqw;
            ki = ki -> left;
        }
        }
        // 计算右子树的高度
        ki = root -> right;
        if(ki){
            ++rqw;
            while(ki -> left) {
            ++rqw;
            ki = ki -> left;
        }
        }
         // 如果左右子树的高度相同，则认为左子树是满二叉树
        if(rqw == lqw) {
            sum += pow(2,lqw + 1) -1;
            judge(root -> right);
        }
        else {
            sum += pow(2.0, rqw +1) -1;
            judge(root -> left);
        }
    }
    // 主函数，返回二叉树的节点总数
    int countNodes(TreeNode* root) {
        if(!root) return 0;// 如果根节点为空，则返回0
        judge(root);// 调用辅助函数进行统计
        return sum;// 返回统计结果
    }
};
